use std::cell::RefCell;
// use std::cmp::max;
use std::collections::{HashMap, VecDeque};
use std::rc::Rc;

// pub mod util; // 报错，一个目录怎么调用另一个目录？

/*
652. 寻找重复的子树
*/

// Definition for a binary tree node.
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None
        }
    }

    // 通过数组反序列化生成一棵树(一维向量/数组转二叉树)
    pub fn vec1d_to_tree_node(nums: Vec<Option<i32>>) -> Option<Rc<RefCell<Self>>> {
        if nums.is_empty() {
            return None;
        }
        let size = nums.len();
        let mut index = 0;
        let root = Some(Rc::new(RefCell::new(Self::new(nums[0].unwrap()))));
        let mut queue = VecDeque::new();
        queue.push_back(root.clone());
        while !queue.is_empty() {
            let q_size = queue.len();
            for _i in 0..q_size {
                if let Some(x) = queue.pop_front().flatten() {
                    // borrow()方法返回内部包装对象的只读引用。
                    // borrow_mut()返回内部包装对象的可写引用。
                    let mut node = x.borrow_mut();
                    let lseq = 2 * index + 1;
                    let rseq = 2 * index + 2;
                    if lseq < size && nums[lseq].is_some() {
                        node.left = Some(Rc::new(RefCell::new(Self::new(nums[lseq].unwrap()))));
                        queue.push_back(node.left.clone());
                    }

                    if rseq < size && nums[rseq].is_some() {
                        node.right = Some(Rc::new(RefCell::new(Self::new(nums[rseq].unwrap()))));
                        queue.push_back(node.right.clone());
                    }
                }
                index += 1;
            }
        }
        root
    }

    pub fn find_duplicate_subtrees(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
        let mut ans = vec![];
        let mut cnt = HashMap::new();

        Self::dfs(&mut ans, &mut cnt, root);

        // 返回的是元素为二叉树的一维数组
        ans
    }

    fn dfs(ans: &mut Vec<Option<Rc<RefCell<TreeNode>>>>, cnt: &mut HashMap<String, i32>, root: Option<Rc<RefCell<TreeNode>>>) -> String {
        if let Some(r) = root {
            let left = Self::dfs(ans, cnt, r.borrow().left.clone());
            let right = Self::dfs(ans, cnt, r.borrow().right.clone());
            let key = format!("{} {} {}", r.borrow().val, left, right);

            *cnt.entry(key.clone()).or_insert(0) += 1;

            if let Some(&v) = cnt.get(&key) {
                if v == 2 {
                    ans.push(Some(r));
                }
            }

            key
        } else {
            ",".to_string()
        }
    }

}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_find_duplicate_subtrees() {
        // 先构造一个二叉树root:
        let nums = vec![
            Some(1),
            Some(2), Some(3),
            Some(4), None, Some(2), Some(4),
            None, None, Some(4)
        ];
        let root = TreeNode::vec1d_to_tree_node(nums);

        // 调用 print_tree
        let ans = TreeNode::find_duplicate_subtrees(root);
        println!("ans: \n{:?}", ans);
        // [Some(RefCell { value: TreeNode { val: 4, left: None, right: None } }), Some(RefCell { value: TreeNode { val: 2, left: Some(RefCell { value: TreeNode { val: 4, left: None, right: None } }), right: None } })]
        // Vec<Option<Rc<RefCell<TreeNode>>>> 怎么转为 Vec<Vec<i32>> ??

    }


}

/*
    // 获取二叉树高度
    pub fn get_tree_node_height(root: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
        fn dfs(root: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
            match root {
                None => 0,
                Some(node) => {
                    let node = node.borrow();
                    // 返回值，直接没有return标识
                    1 + max(dfs(&node.left), dfs(&node.right))
                }
            }
        }
        dfs(&root)
    }

    // leetcode 655. 输出二叉树(树的拓扑树形进行打印)(leetcode这个题输出的是vec，和这个不太一样!!)
    pub fn print_tree_as_string(root: Option<Rc<RefCell<TreeNode>>>) -> String {
        // 二叉树高度
        let height = TreeNode::get_tree_node_height(&root);
        // 满二叉树的宽度
        let width = (1 << height) - 1;
        let mut ans = vec![vec![" ".to_string(); width as usize]; height as usize];

        // dfs 搜索
        fn dfs(ans: &mut Vec<Vec<String>>, node: &Option<Rc<RefCell<TreeNode>>>, deep: usize, lo: usize, hi: usize) {
            if let Some(x) = node {
                let node = x.borrow();
                let mid = lo + (hi - lo) / 2;
                ans[deep][mid] = x.borrow().val.to_string();
                dfs(ans, &node.left, deep + 1, lo, mid);
                dfs(ans, &node.right, deep + 1, mid + 1, hi);
            }
        }

        dfs(&mut ans, &root, 0usize, 0usize, width as usize);
        // 将所有字符连起来
        ans.iter().map(|x| x.concat()).collect::<Vec<_>>().join("\n")
    }

    // 自己写的：二叉树数组转字符串
    pub fn tree_node_array_to_string(ans: Vec<Option<Rc<RefCell<TreeNode>>>>) -> Vec<String> {
        let mut out = Vec::new();
        for i in ans.iter() {
            // println!(i);
            // cannot find function `print_tree_as_string` in module `self`
            // out.push(self::print_tree_as_string(i.clone()))
            out.push(TreeNode::print_tree_as_string(i.clone()))
        }
        out
    }
*/

// pub mod SolutionFindDuplicateSubtrees {}
//
// // 652. 寻找重复的子树
// impl SolutionFindDuplicateSubtrees {
//     // not a type
//     // expected type, found module `SolutionFindDuplicateSubtrees`
//     // 运行print_tree.rs，关这个文件什么事儿？？？
//     // 同一个.rs文件，只能只能有一个impl？？？
//     pub fn find_duplicate_subtrees(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
//         let mut ans = vec![];
//         let mut cnt = HashMap::new();
//
//         Self::dfs(&mut ans, &mut cnt, root);
//
//         // 返回的是元素未二叉树的一维数组
//         ans
//     }
//
//     fn dfs(ans: &mut Vec<Option<Rc<RefCell<TreeNode>>>>, cnt: &mut HashMap<String, i32>, root: Option<Rc<RefCell<TreeNode>>>) -> String {
//         if let Some(r) = root {
//             let left = Self::dfs(ans, cnt, r.borrow().left.clone());
//             let right = Self::dfs(ans, cnt, r.borrow().right.clone());
//             let key = format!("{} {} {}", r.borrow().val, left, right);
//
//             *cnt.entry(key.clone()).or_insert(0) += 1;
//
//             if let Some(&v) = cnt.get(&key) {
//                 if v == 2 {
//                     ans.push(Some(r));
//                 }
//             }
//
//             key
//         } else {
//             ",".to_string()
//         }
//     }
//
// }
